//编写一个程序，通过填充空格来解决数独问题。 
//
// 数独的解法需 遵循如下规则： 
//
// 
// 数字 1-9 在每一行只能出现一次。 
// 数字 1-9 在每一列只能出现一次。 
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 
// 
//
// 数独部分空格内已填入了数字，空白格用 '.' 表示。 
//
// 
//
// 
// 
// 
// 示例： 
//
// 
//输入：board = [['5','3','.','.','7','.','.','.','.'],['6','.','.','1','9','5','.'
//,'.','.'],['.','9','8','.','.','.','.','6','.'],['8','.','.','.','6','.','.','.'
//,'3'],['4','.','.','8','.','3','.','.','1'],['7','.','.','.','2','.','.','.','6'
//],['.','6','.','.','.','.','2','8','.'],['.','.','.','4','1','9','.','.','5'],['
//.','.','.','.','8','.','.','7','9']]
//输出：[['5','3','4','6','7','8','9','1','2'],['6','7','2','1','9','5','3','4','8'
//],['1','9','8','3','4','2','5','6','7'],['8','5','9','7','6','1','4','2','3'],['
//4','2','6','8','5','3','7','9','1'],['7','1','3','9','2','4','8','5','6'],['9','
//6','1','5','3','7','2','8','4'],['2','8','7','4','1','9','6','3','5'],['3','4','
//5','2','8','6','1','7','9']]
//解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
//
//
// 
//
// 
//
// 提示： 
//
// 
// board.length == 9 
// board[i].length == 9 
// board[i][j] 是一位数字或者 '.' 
// 题目数据 保证 输入数独仅有一个解 
// 
// 
// 
// 
// Related Topics 数组 回溯 矩阵 
// 👍 1040 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class SudokuSolver {
    public static void main(String[] args) {
        char[][] chars = {{'5','3','.','.','7','.','.','.','.'},
                          {'6','.','.','1','9','5','.','.','.'},
                          {'.','9','8','.','.','.','.','6','.'},
                          {'8','.','.','.','6','.','.','.','3'},
                          {'4','.','.','8','.','3','.','.','1'},
                          {'7','.','.','.','2','.','.','.','6'},
                          {'.','6','.','.','.','.','2','8','.'},
                          {'.','.','.','4','1','9','.','.','5'},
                          {'.','.','.','.','8','.','.','7','9'}};

        new SudokuSolver().new Solution().solveSudoku(chars);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 马踏棋盘，八皇后，还有数独都是回溯算法的应用，不断的尝试
     * 我这个写的几分钟都没出结果，主要是如何进行回溯的优化
     * 思路如下：
     * 1.遍历board，发现不是数字的话就进行赋值
     *      赋值的时候要保证当前行，列，区域内不存在此值 进行添加，并向下一个位置进行dfs
     * 2.失败后返回要删除行、列、区域添加的值，并将board恢复成为'.'
     *
     * 递归返回值一定为Boolean，便于判断递归结束时机，返回值为true说明找到了，就不用恢复状态了
     * 我这个是使用了9个行，9个列，9个区域来存储信息，遍历时需要根据这三个值来判断k是否合适
     *
     * 判断是否重复可以根据棋盘和坐标来进行判断，我这个是先分好了空间
     */
    class Solution {
        public void solveSudoku(char[][] board) {
            List<List<Character>> rows = new ArrayList<>();
            List<List<Character>> cols = new ArrayList<>();
            List<List<Character>> area = new ArrayList<>();
            for (int i = 0; i < 9; i++) {
                rows.add(new ArrayList<>());
                cols.add(new ArrayList<>());
                area.add(new ArrayList<>());
            }
            for (int i = 0; i < 9 ; i++) {
                for (int j = 0; j < 9; j++) {
                    if (Character.isDigit(board[i][j])){
                        char temp = board[i][j];
                        rows.get(i).add(temp);
                        cols.get(j).add(temp);
                        area.get(whichArea(i,j)).add(temp);
                    }
                }
            }
            dfs(board, rows, cols, area);
            System.out.println("stop");

        }
        public boolean dfs(char[][] board,List<List<Character>> rows,List<List<Character>> cols,List<List<Character>> area){
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == '.'){
                        for (char k = '1'; k <= '9'; k++) {
                            if (!rows.get(i).contains(k)&&!cols.get(j).contains(k)&&!area.get(whichArea(i,j)).contains(k)){
                                List<Character> tempRow = rows.get(i);
                                List<Character> tempCol = cols.get(j);
                                List<Character> tempArea = area.get(whichArea(i, j));
                                board[i][j] = k;
                                tempRow.add(k);
                                tempCol.add(k);
                                tempArea.add(k);
                                // TODO 这里如果成功一定要返回，否则下边的代码会重置状态
                                if (dfs(board, rows, cols, area)) return true;
                                // 一定是失败之后再重置状态，否则白干了
                                board[i][j] = '.';
                                tempRow.remove(tempRow.size()-1);
                                tempCol.remove(tempCol.size()-1);
                                tempArea.remove(tempArea.size()-1);
                            }
                        }
                        return false;//9个数字都试过了，说明没找到合适的，返回false
                    }
                }
            }
            return true;//能遍历到这里说明棋盘已经好了，直接返回true
        }
        public int whichArea(int x, int y){
            return x/3*3 + y/3;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    /**
     * 这是题解中的方法，思路是一样的，就是判断是否重复不一样
     */
    class Solution2 {
        public void solveSudoku(char[][] board) {
            solveSudokuHelper(board);
        }

        private boolean solveSudokuHelper(char[][] board){
            //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
            // 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
            for (int i = 0; i < 9; i++){ // 遍历行
                for (int j = 0; j < 9; j++){ // 遍历列
                    if (board[i][j] != '.'){ // 跳过原始数字
                        continue;
                    }
                    for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
                        if (isValidSudoku(i, j, k, board)){
                            board[i][j] = k;
                            if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    // 9个数都试完了，都不行，那么就返回false
                    return false;
                    // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                    // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
                }
            }
            // 遍历完没有返回false，说明找到了合适棋盘位置了
            return true;
        }

        /**
         * 判断棋盘是否合法有如下三个维度:
         *     同行是否重复
         *     同列是否重复
         *     9宫格里是否重复
         */
        private boolean isValidSudoku(int row, int col, char val, char[][] board){
            // 同行是否重复
            for (int i = 0; i < 9; i++){
                if (board[row][i] == val){
                    return false;
                }
            }
            // 同列是否重复
            for (int j = 0; j < 9; j++){
                if (board[j][col] == val){
                    return false;
                }
            }
            // 9宫格里是否重复
            int startRow = (row / 3) * 3;
            int startCol = (col / 3) * 3;
            for (int i = startRow; i < startRow + 3; i++){
                for (int j = startCol; j < startCol + 3; j++){
                    if (board[i][j] == val){
                        return false;
                    }
                }
            }
            return true;
        }
    }
    //TODO 二刷的时候还是感觉根据区域起始下标去遍历更简洁一些
    public boolean valid(char c, int row, int col, char[][] board){
        for (int i = 0; i < 9; i++) if (board[row][i] == c) return false;
        for (int i = 0; i < 9; i++) if (board[i][col] == c) return false;
        int rowStart = row/3*3, colStart = col/3*3;//区域起始下标
        for(int i = rowStart; i < rowStart+3; i++){
            for (int j = colStart; j < colStart+3;j++)
                if (board[i][j] == c) return false;
        }
        return true;
    }

}